/*************************************************************************
> File Name: binary_lookup.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-23 23:29:39
> Description: 二分查找
************************************************************************/

#include <stdio.h>

int binaryLookup(int arr[], int length, int target);
int main(int argc, char const *argv[])
{
    int arr[100] = {0};
    for (int i = 0; i < 100; i++)
    {
        arr[i] = i;
    }
    int target = 0;
    int targetSuffix = -1;
    targetSuffix = binaryLookup(arr, 100, target);
    printf("target %d suffix is %d\n", target, targetSuffix);
    target = 74;
    targetSuffix = binaryLookup(arr, 100, target);
    printf("target %d suffix is %d\n", target, targetSuffix);
    for (int i = 0; i < 100; i++)
    {
        target = i;
        targetSuffix == -1;
        targetSuffix = binaryLookup(arr, 100, target);
        if (targetSuffix == -1)
        {
            printf("!!%d!!", i);
        }
    }

    return 0;
}

int binaryLookup(int arr[], int length, int target)
{
    // 不在数组范围
    if (arr[0] > target || arr[length - 1] < target)
    {
        return -1;
    }
    int targetSuffix = -1;
    int left = 0, right = length - 1, mid = left + (right - left) / 2;
    while (left <= right) // 小于等于 有可能出现左右相同！！指向同一个数
    {

        if (arr[mid] == target)
        {
            targetSuffix = mid;
            break;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1; // 加一 避开中间值
        }
        else if (arr[mid] > target)
        {
            right = mid - 1; // 减一
        }
        mid = left + (right - left) / 2;
    }
    return targetSuffix;
}
